package linkedList.递归.剑指;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 剑指Offer复杂链表的复制35.java
 * @Description TODO
 * @createTime 2021年03月22日 11:33:00
 */
public class 剑指Offer复杂链表的复制35 {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     * -10000 <= Node.val <= 10000
     * Node.random 为空（null）或指向链表中的节点。
     * 节点数目不超过 1000 。
     */
    public static Node copyRandomList(Node head) {
        Node p = head;
        while (p != null) {
            Node temp = new Node(p.val);
            temp.next = p.next;
            p.next = temp;
            p = temp.next;
        }
        p = head;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        Node pre = new Node(-1);
        p = head;
        Node temp = pre;
        while (p != null) {
            temp.next=p.next;
            temp=temp.next;
            p.next=temp.next;
            p=p.next;
        }
        return pre.next;
    }

    public static Node copyRandomListError(Node head) {
        //todo 挨个复制一次节点
        Node p = head;
        Node node = copyNode(p);
        //todo 设置新增的节点的random
        p = head;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        //todo 进行分离
        return separate(head);
    }

    private static Node separate(Node p) {
        if (p == null) {
            return p;
        }
        p.next = separate(p.next.next);
        return p;
    }

    private static Node copyNode(Node p) {
        if (p == null) {
            return p;
        }
        Node node = copyNode(p.next);
        Node temp = new Node(p.val);
        p.next = temp;
        temp.next = node;
        return p;
    }

    public static void main(String[] args) {
        剑指Offer复杂链表的复制35.Node node = new 剑指Offer复杂链表的复制35.Node(1);
        剑指Offer复杂链表的复制35.Node node1 = new 剑指Offer复杂链表的复制35.Node(2);
        剑指Offer复杂链表的复制35.Node node2 = new 剑指Offer复杂链表的复制35.Node(3);
        剑指Offer复杂链表的复制35.Node node3 = new 剑指Offer复杂链表的复制35.Node(4);
        node.random = node3;
        node1.random = null;
        node2.random = node1;
        node3.random = node2;
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        剑指Offer复杂链表的复制35.Node list = copyRandomList(node);
        System.out.println(list);
    }
}
